#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;

class Solution{
    private:
    vector<vector<int>> ret;

    public:
    vector<vector<int>> ans1(vector<int>& nums){
        vector<int> temp;
        unordered_set<int> c;
        vector<int> rem;
        add(temp, nums);
        for(int i = 0; i != ret.size(); i++){
            for(int j = 0; j != ret[i].size(); j++){
                if(c.count(ret[i][j]) != 0){
                    rem.push_back(i);
                    break;
                }else{
                    c.insert(ret[i][j]);
                }
            }
            c.clear();
        }

        for(int i = 0; i != rem.size(); i++){
            ret.erase(ret.begin() + rem[rem.size() - 1- i]);
        }

        return ret;
    }

    void add(vector<int>& temp, vector<int>& nums){
        if(temp.size() == nums.size()){
            ret.push_back(temp);
        }else{
            for(int i = 0; i != nums.size(); i++){
                temp.push_back(nums[i]);
                add(temp, nums);
                temp.pop_back();
            }
        }
    }

    vector<vector<int>> ans2(vector<int>& nums){
        back(nums, 0);

        return ret;
    }

    void back(vector<int>& nums, int first){
        if(first == nums.size()){
            ret.push_back(nums);
        }else{
            for(int i = first; i != nums.size(); i++){
                swap(nums[i], nums[first]);
                back(nums, first+1);
                swap(nums[i], nums[first]);
            }
        }
        
    }
};

void test(){
    Solution s;
    vector<int> nums = {1,2,3};
    // vector<vector<int>> ret = s.ans1(nums);
    vector<vector<int>> ret = s.ans2(nums);
    for(int i = 0; i != ret.size(); i++){
        for(int j = 0; j != ret[0].size()-1; j++){
            cout << ret[i][j] << " " << ends;
        }
        cout << ret[i][ret[0].size()-1] << endl;
    }
}

int main(void){
    test();

    return 0;
}